package com.tgy.algorithm.base._图_01;


import java.util.*;

public class _拓扑排序 {


    /*
     *  {
     *     {0,1,2},
     *     {0,2,3},
     *     {1,3,2},
     *     {2,3,2}
     * }
     */
    public static Graph<Integer> createGraph(int[][] datas) {

        Graph<Integer> graph = new Graph<>();

        for (int i = 0; i < datas.length; i++) {
            int[] info = datas[i];
            int from = info[0];
            int to = info[1];
            int weight = info[2];

            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node<>(from));
            }

            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node<>(to));
            }

            Node<Integer> fromNode = graph.nodes.get(from);

            Node<Integer> toNode = graph.nodes.get(to);
            toNode.in++;
            fromNode.out++;
            fromNode.nexts.add(toNode);

            Edge<Integer> edge = new Edge<>(weight, fromNode, toNode);
            graph.edges.add(edge);
            fromNode.edges.add(edge);
        }

        return graph;
    }


    public static List<Integer> topologicalSort(Graph<Integer> graph) {

        List<Integer> res = new ArrayList<>();
        HashMap<Node<Integer>, Integer> map = new HashMap<>();

        Node<Integer> node = null;
        for (Node<Integer> value : graph.nodes.values()) {
            map.put(value,value.in);
            if (value.in == 0) {
                node = value;
            }
        }

        if (node == null) {
            return res;
        }

        Queue<Node<Integer>> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
            Node<Integer> selectNode = queue.poll();
            res.add(selectNode.value);
            for (Node<Integer> next : selectNode.nexts) {
                map.put(next,map.get(next) - 1);
                if (map.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }

        return res;
    }


    public static void main(String[] args) {
        Graph<Integer> graph = createGraph(new int[][]{{0, 1, 2}, {0, 2, 3}, {1, 3, 2}, {2, 3, 2}});
        System.out.println(graph);
        List<Integer> res = topologicalSort(graph);
        System.out.println(res);
    }
}
